package com.leet.code.lcof;

import java.util.ArrayList;

public class Code51 {

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7};
        System.out.println(new Code51().reversePairs(nums));

    }

    ArrayList<Integer> list;

    public int reversePairs(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        list = new ArrayList<>(nums.length);
        list.add(nums[nums.length - 1]);
        int sum = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            sum = sum + sort(nums, i);
        }
        return sum;
    }


    public int sort(int[] nums, int i) {
        int index = search(nums[i]);
        list.add(index, nums[i]);
        return index;
    }

    public int search(int i) {
        int s = 0;
        int e = list.size() - 1;

        int m;
        while (s < e) {
            m = (s + e) >> 1;
            int j = list.get(m);

            if (j == m) {
                break;
            } else if (j > i) {
                e = m - 1;
            } else {
                s = m + 1;
            }

        }

        m = (s + e) >> 1;

        if (m < 0) {
            m = 0;
        }

        while (m != 0 && list.get(m) >= i) {
            m--;
        }
        while (m < list.size() && list.get(m) < i) {
            m++;
        }
        return m;
    }


}
